/* ==================================================================
 * Copyright (c) 2024/11/15 SCNU LiuJunJie z-ken
 * All rights reserved.
 * fileName:	NFAToDFA.hpp
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the
 * distribution.
 * 3. All advertising materials mentioning features or use of this software
 * must display the following acknowledgement:
 * This product includes software developed by the xxx Group. and
 * its contributors.
 * 4. Neither the name of the Group nor the names of its contributors may
 * be used to endorse or promote products derived from this software
 * without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY Author,GROUP AND CONTRIBUTORS
 * ===================================================================
 * Author: LiuJunJie z-ken.
 */

#include "Base.hpp"
#include "libs.hpp"
#include "func_read.hpp"
#include "MyObject.hpp"

#if !defined(NFA_TO_DFA)
#define NFA_TO_DFA

class DFA_Builder
{
public:
    vector<vector<vector<int>>> NFA; // 定义：行是节点编号，列是re的序号，存放的是下一个状态的节点编号
    int nfa_start, nfa_end;
    vector<Base> baseState; // 记录所有的加入的基本re

    map<string, map<string, string>> DFA; // 记录添加了的集合，定义：集合str-》该集合对应的关系表的map-》走过此关系后的集合

    map<string, map<string, string>> minDFA;  // 记录添加了的集合，定义：集合str-》该集合对应的关系表的map-》走过此关系后的集合
    map<string, map<string, string>> minDFA2; // 记录添加了的集合，定义：集合str-》该集合对应的关系表的map-》走过此关系后的集合
    map<string, map<string, string>> minDFA2_temp;
    map<int, map<string, int>> state_DFA;     // 集合变化为状态的DFA
    map<int, map<string, int>> state_min_DFA; // 集合变化为状态的DFA

    set<int> startState; // 变换为状态DFA后，分类为终点state和起点state
    set<int> endState;   // 变换为状态DFA后，分类为终点state和起点state

    map<string, vector<int>> str_vector; // 字符串转vector
    map<string, int> isTerminal;         // 判断是集合是否是终态，现在不使用了，

    set<int> destination;
    set<int> unDestination;

public:
    void make()
    {
        this->search();
    }

    void setBaseState(vector<Base> t)
    {
        baseState = t;
    }
    void setNFA(vector<vector<vector<int>>> NFA_in, int st1, int ed1)
    {
        this->NFA = NFA_in;

        nfa_start = st1;
        nfa_end = ed1;
    }

    string vectorToString(vector<int> &t)
    {
        string res = "{";
        for (auto p : t)
        {
            res += to_string(p) + ",";
        }
        res += "}";
        return res;
    }

    vector<int> stringToIntVector(string s)
    {
        vector<int> res;
        int temp = 0;
        for (int i = 1; i < s.size() - 1; i++)
        {
            if (isdigit(s[i]))
            {
                temp = temp * 10 + (s[i] - '0');
            }
            else
            {
                res.push_back(temp);
                temp = 0;
            }
        }
        return res;
    }

    bool check_InRecord(vector<int> &t)
    {
        string t2 = vectorToString(t);
        DFA.find(t2);
        return DFA.find(t2) != DFA.end();
    }
    void search()
    {
        queue<vector<int>> q;             // 记录节点号
        vector<int> t;                    // 作为引用来被下方函数调用
        searchBySigemaEdge(nfa_start, t); // 获取空节点的集合(当前集合区域)
        q.push(t);
        while (!q.empty())
        {
            vector<int> curr = q.front();
            q.pop();
            // 遍历所有状态
            if (check_InRecord(curr) == true || curr.empty())
            {
                continue;
            }
            for (int i = 0; i < baseState.size(); i++) // 枚举所有状态
            {
                vector<int> t2;                          // 准备加入队列的集合
                for (int i2 = 0; i2 < curr.size(); i2++) // 枚举curr有关空集合的每个节点
                {
                    int row1 = curr[i2];
                    vector<int> &next1 = NFA[row1][i];        // 该节点经过某状态的集合
                    for (int i3 = 0; i3 < next1.size(); i3++) // 枚举该节点经过某状态的集合
                    {
                        int val = next1[i3];
                        if (!inContainer(t2, val))
                        {
                            searchBySigemaEdge(val, t2);
                        }
                    }
                }
                if (i == 0)
                {
                    t2 = curr;
                }
                // 可以访问的集合一定可加入
                string curr_str = vectorToString(curr);
                str_vector[curr_str] = curr; // 记录转换方式
                DFA[curr_str][baseState[i].regular_Expression] = vectorToString(t2);
                q.push(t2);
            }
        }
    }

    // 此处构建的是标准DFA的情况下的state
    void buildStateDFA()
    {
        startState.clear();
        endState.clear();

        state_DFA.clear();
        // 行
        map<string, int> hashState;
        int cnt1 = 1;
        for (auto p : DFA)
        {
            if (p.first == "#")
            {
                continue;
            }
            hashState[p.first] = cnt1;
            vector<int> temp = stringToIntVector(p.first);
            set<int> s(temp.begin(), temp.end());
            // 分辨是终点还是起点抑或是中间状态，或者是两种状态重合
            if (s.find(nfa_start) != s.end())
            {
                startState.insert(cnt1);
            }
            if (s.find(nfa_end) != s.end())
            {
                endState.insert(cnt1);
            }
            cnt1 += 1;
        }

        for (auto p : DFA)
        {
            // baseState默认一号位置是# 空符号，可以省略
            for (int i = 1; i < baseState.size(); i++)
            {
                // 获取一个可能走的边
                string re_tmp = baseState[i].regular_Expression;
                if (hashState.find(p.second[re_tmp]) != hashState.end())
                {
                    state_DFA[hashState[p.first]][re_tmp] = hashState[p.second[re_tmp]];
                }
                else
                {
                    state_DFA[hashState[p.first]][re_tmp] = -1;
                }
            }
        }
    }

    void showStateDFA()
    {
        cout << "展示DFA的StateDFA" << endl;

        cout << "self:";
        // baseState默认一号位置是# 空符号，可以省略不输出
        for (int i = 1; i < baseState.size(); i++)
        {
            cout << '\t' << to_string(i) + ":" + baseState[i].regular_Expression;
        }
        cout << endl;
        for (auto p : state_DFA)
        {
            cout << p.first << "\t";
            // baseState默认一号位置是# 空符号，可以省略不输出
            for (int i = 1; i < baseState.size(); i++)
            {
                // 获取一个可能走的边
                string re_tmp = baseState[i].regular_Expression;
                cout << p.second[re_tmp] << "\t";
            }
            cout << endl;
        }
    }

    // 此处构建的是标准DFA的情况下的state
    void buildStateMinDFA()
    {
        // 清空记录的起点状态和终点状态
        startState.clear();
        endState.clear();
        state_min_DFA.clear();
        // 行
        map<string, int> hashState;
        // 记录最小化的DFA有多少个状态
        vector<string> states;
        int cnt1 = 1; // 状态计数器，记录死第几个状态
        for (auto p : minDFA2)
        {
            if (p.first == "#")
            {
                continue;
            }
            hashState[p.first] = cnt1;
            states.push_back(p.first);
            vector<int> temp = stringToIntVector(p.first);
            set<int> s(temp.begin(), temp.end());
            // 分辨是终点还是起点抑或是中间状态，或者是两种状态重合
            if (s.find(nfa_start) != s.end())
            {
                startState.insert(cnt1);
            }
            if (s.find(nfa_end) != s.end())
            {
                endState.insert(cnt1);
            }
            cnt1 += 1;
        }

        for (auto p : minDFA2)
        {
            // baseState默认一号位置是# 空符号，可以省略
            for (int i = 1; i < baseState.size(); i++)
            {
                // 获取一个可能走的边
                string re_tmp = baseState[i].regular_Expression;
                string next_t = p.second[re_tmp];
                vector<int> t = stringToIntVector(next_t);
                set<int> st = set<int>(t.begin(), t.end()); // 到达的状态

                if (st.size() == 0)
                {
                    // hashState[p.first]是状态对应的状态序号
                    state_min_DFA[hashState[p.first]][re_tmp] = -1;
                }
                else // 如果终点到达的集合状态被包含在某一个状态（被包含关系）
                {
                    // 替换被包含关系的状态
                    /*
                    由于到达的下一个状态集合可能所有状态集合的一个子集，所以需要在此处进行判断，找到属于的那一个状态集合，然后终点记录为其的状态序号
                    */
                    for (string hashState_first : states)
                    {
                        set<int> state = stringToSet(hashState_first);
                        set<int> temp = st;
                        for (int state_i : state)
                        {
                            temp.erase(state_i);
                        }
                        if (temp.size() == 0)
                        {
                            state_min_DFA[hashState[p.first]][re_tmp] = hashState[hashState_first];
                            break;
                        }
                    }
                }
            }
        }
    }

    void showStateMinDFA()
    {
        cout << "展示DFA的showStateMinDFA" << endl;

        cout << "self:";
        // baseState默认一号位置是# 空符号，可以省略不输出
        for (int i = 1; i < baseState.size(); i++)
        {
            cout << '\t' << to_string(i) + ":" + baseState[i].regular_Expression;
        }
        cout << endl;
        for (auto p : state_min_DFA)
        {
            cout << p.first << "\t";
            // baseState默认一号位置是# 空符号，可以省略不输出
            for (int i = 1; i < baseState.size(); i++)
            {
                // 获取一个可能走的边
                string re_tmp = baseState[i].regular_Expression;
                cout << p.second[re_tmp] << "\t";
            }
            cout << endl;
        }
    }

    void searchBySigemaEdge(int start1, vector<int> &t)
    {
        t.push_back(start1);

        vector<int> temp = NFA[start1][0];
        for (int i = 0; i < temp.size(); i++)
        {
            if (!inContainer(t, temp[i]))
            {
                searchBySigemaEdge(temp[i], t);
            }
        }
        return;
    }

    bool inContainer(vector<int> &t, int val)
    {
        for (auto p : t)
        {
            if (val == p)
            {
                return true;
            }
        }
        return false;
    }

    void showDFA()
    {
        if (SHOW_DFA == 0)
        {
            return;
        }

        ios_base::fmtflags defaultFlags = cout.flags();
        streamsize defaultWidth = cout.width();
        cout << "DFA2的内容" << endl;

        // 列坐标
        cout << left;
        cout << setw(M_OUTPUT_LEN) << "re:";
        cout << setw(M_OUTPUT_LEN) << "self:";
        for (int i = 1; i < baseState.size(); i++)
        {
            cout << setw(M_OUTPUT_LEN) << to_string(i) + ":" + baseState[i].regular_Expression;
        }
        cout << endl;

        // 行
        int r = 1;
        for (auto p : DFA)
        {
            cout << setw(M_OUTPUT_LEN) << "row:" + to_string(r++) + ": ";
            // cout << setw(M_OUTPUT_LEN) << p.first;
            for (int i = 0; i < baseState.size(); i++)
            {
                cout << setw(M_OUTPUT_LEN) << p.second[baseState[i].regular_Expression];
            }
            cout << endl;
        }

        // 恢复默认的输出格式
        cout.flags(defaultFlags);
        cout.width(defaultWidth);
    }

    void showMinDFA2()
    {
        if (SHOW_MINDFA == 0)
        {
            return;
        }

        ios_base::fmtflags defaultFlags = cout.flags();
        streamsize defaultWidth = cout.width();
        cout << "minDFA2的内容 ，其中空状态没有意义" << endl;

        // 列坐标
        cout << left;
        cout << setw(M_OUTPUT_LEN) << "re:";
        cout << setw(M_OUTPUT_LEN) << "self:";
        for (int i = 0; i < baseState.size(); i++)
        {
            cout << setw(M_OUTPUT_LEN) << to_string(i) + ":" + baseState[i].regular_Expression;
        }
        cout << endl;

        // 行
        int r = 1; // r可以理解为状态号码
        for (auto p : minDFA2)
        {
            cout << setw(M_OUTPUT_LEN) << "row:" + to_string(r++) + ": ";
            cout << setw(M_OUTPUT_LEN) << p.first;
            for (int i = 0; i < baseState.size(); i++)
            {
                cout << setw(M_OUTPUT_LEN) << p.second[baseState[i].regular_Expression];
            }
            cout << endl;
        }

        // 恢复默认的输出格式
        cout.flags(defaultFlags);
        cout.width(defaultWidth);
    }

    void buildDestination()
    {
        set<int> total;
        for (auto p : str_vector)
        {
            vector<int> &set1 = p.second;
            if (inContainer(set1, nfa_end))
            {
                isTerminal[p.first] = 1;
                for (auto p2 : set1)
                {
                    destination.insert(p2);
                }
            }

            for (auto p2 : set1)
            {
                total.insert(p2);
            }
        }

        unDestination = total;
        for (auto p : destination)
        {
            unDestination.erase(p);
        }

        // cout << "terminal状态集合：";
        // for (auto p : isTerminal)
        // {
        //     cout << p.first << " ";
        // }
        // cout << endl;

        // cout << "总集合为";
        // for (auto p : total)
        // {
        //     cout << p << " ";
        // }
        // cout << endl;

        // cout << "出发点集合为";
        // for (auto p : unDestination)
        // {
        //     cout << p << " ";
        // }
        // cout << endl;

        // cout << "terminal的集合为";
        // for (auto p : destination)
        // {
        //     cout << p << " ";
        // }
        // cout << endl;

        vector<int> destination_copy(destination.begin(), destination.end());
        str_vector[vectorToString(destination_copy)] = destination_copy;
    }

    void minilize()
    {
        // 开始构造新的miniDFA2
        minDFA2 = DFA;
        cout << "正在最小化，执行以下操作中" << endl;
        while (1)
        {
            minDFA2_temp = minDFA2;  // 迭代最小化
            bool hasChanged = false; // 是否发生合并

            for (auto p : minDFA2_temp)
            {
                if (hasChanged == true)
                {
                    break;
                }
                for (auto p2 : minDFA2_temp)
                {
                    if (hasChanged == true)
                    {
                        break;
                    }
                    if (p2.first == p.first) // 确保不重复
                    {
                        continue;
                    }
                    if (couldMerge(p.first, p2.first)) // p和p2行可以融合（可以融合：指代所有运算结果一致都属于终点；）
                    {
                        // 先移除，后合并
                        minDFA2.erase(p.first);
                        minDFA2.erase(p2.first);

                        vector<int> v1 = str_vector[p.first];
                        vector<int> v2 = str_vector[p2.first];
                        set<int> set1(v1.begin(), v1.end());
                        set<int> set2(v2.begin(), v2.end());
                        for (auto set2_i : set2)
                        {
                            set1.insert(set2_i);
                        }
                        vector<int> newRow(set1.begin(), set1.end()); // 合并，产生新的集合
                        string newRow_str = vectorToString(newRow);
                        for (auto p3 : p.second) // 遍历所有运算方式
                        {
                            vector<int> p3_v1 = str_vector[minDFA2_temp[p.first][p3.first]];
                            vector<int> p3_v2 = str_vector[minDFA2_temp[p.first][p3.first]];
                            set<int> p3_set1(p3_v1.begin(), p3_v1.end());
                            set<int> p3_set2(p3_v2.begin(), p3_v2.end());
                            for (auto p3_set2_i : p3_set2)
                            {
                                p3_set1.insert(p3_set2_i);
                            }

                            vector<int> newData(p3_set1.begin(), p3_set1.end());
                            string newData_str = vectorToString(newData);
                            str_vector[newData_str] = newData;
                            minDFA2[newRow_str][p3.first] = newData_str;

                            // minDFA2[newRow_str][p3.first] = p3.second;
                        }
                        // cout << p.first << " and " << p2.first << "合并为" << newRow_str << endl;
                        str_vector[newRow_str] = newRow; // 将新合并的记录到抓换中

                        hasChanged = true;
                    }
                }
            }

            if (hasChanged == false)
            {
                break;
            }
            // showMinDFA2();
        }

        showMinDFA2();
    }

    void minilizeState()
    {
    }

    bool setCompleteInDestination(set<int> s1) // 属于终点的子集
    {
        for (auto p : destination)
        {
            s1.erase(p);
        }
        return s1.empty();
    }

    /**
     * 如果是空，返回1，如果是起点集合的一部分，返回1，如果是终点集合的一部分，返回2
     */
    int getSetState(set<int> set1)
    {
        if (set1.size() == 0)
        {
            return 0;
        }
        if (setCompleteInDestination(set1))
        {
            return 2;
        }
        else
        {
            return 1;
        }
    }

    bool couldMerge(string s1, string s2) // （可以融合：指代所有运算结果一致都属于终点；）
    {
        // 集合状态是终点还是非终点，不一致的不可以合并
        set<int> s1_set = stringToSet(s1);
        set<int> s2_set = stringToSet(s2);
        int s1_state = s1_set.find(nfa_end) != s1_set.end();
        int s2_state = s2_set.find(nfa_end) != s2_set.end();
        if (s1_state != s2_state)
        {
            return false;
        }

        for (auto p : minDFA2_temp[s1]) // 在2个行的进行讨论
        {
            if (p.first != "#")
            {
                vector<int> v1 = str_vector[minDFA2_temp[s1][p.first]];
                vector<int> v2 = str_vector[minDFA2_temp[s2][p.first]];
                unordered_set<int> set1(v1.begin(), v1.end());
                unordered_set<int> set2(v2.begin(), v2.end());

                // 全空或者都不为空，进行和终点的集合判断
                if (set1 != set2) // 存在一个集合不是终点子集或者都不是的时候就不要可以合并；
                {
                    return false;
                }
            }
        }

        return true; // 对所有re运算产生的结果都一致的时候，返回真
    }

    set<int> stringToSet(string str)
    {
        vector<int> v = stringToIntVector(str);
        return set<int>(v.begin(), v.end());
    }
};

#endif // NFA_TO_DFA
